package com.lry.basic.algorithm.common;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/11
 */
//        给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
//        示例 1:
//        输入: nums = [1,1,1,2,2,3,4,4,4], k = 2
//        输出: [1,4]
public class TopKFrequent {
    public static void main(String[] args) {
        List<Integer> res = topKFrequent(new int[]{1,1,1,2,2,3,4,4,4,5,5,5,5},2);
        for (Integer i:res) {
            System.out.println(i);
        }
    }

    public static List<Integer> topKFrequent(int[] nums, int k) {
        if(null==nums||nums.length==0||k>nums.length){
            return null;
        }
        //<数字，次数>
        Map<Integer,Integer> map = new HashMap<>();
        for (int num:nums) {
            Integer count = map.get(num);
            if(null==count)count=0;
            map.put(num,count+1);
        }
        //桶排序思路，用次数作为数组下标,数组元素里面存储多个出现相同次数的数字，例如[1,1,1,2,2,3,4,4,4]，下标3(次数)存储1和4
        List<Integer>[] bucket = new ArrayList[nums.length+1];
        for (int key:map.keySet()) {
            int count = map.get(key);
            if(null==bucket[count]){
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(key);
        }
        List<Integer>res = new ArrayList<>();
        for(int i=bucket.length-1;i>=0&&res.size()<k;i--){
            if(null!=bucket[i]){
                for (int j:bucket[i]) {
                    if(res.size()<k)
                    res.add(j);
                }
            }
        }
        return res;
    }
}
